package leetcode.Hot100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 0 <= s.length <= 3 * 10^4
 * s[i] 为 '(' 或 ')'
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 * @version 1.0
 * @date 2021/12/31 15:33
 * 技巧性很强的一道 困难题
 */
public class longestValidParentheses {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses0("(()()"));
    }

    // 本题的LeetCode精选评论的思路
    // https://leetcode-cn.com/problems/longest-valid-parentheses/comments/
    // 将字符串中的所有字符入栈，能匹配的位置用 0 表示，不能匹配的位置用1 表示
    // 例如: "()(()" 转换为[0, 0, 1, 0, 0]
    // 再例如: ")()((())" 转换为[1, 0, 0, 1, 0, 0, 0, 0]
    // 经过这样的处理后, 此题就变成了寻找最长的连续的0的长度
    static public int longestValidParentheses0(String s) {
        int length = s.length();
        Deque<Integer> stack = new LinkedList<>();
        // 转换后的 标识数组，能匹配的位置用 0 表示，不能匹配的位置用1 表示
        int[] markArr = new int[length];
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }else {
                // 栈为空,则这个右括号不能匹配
                if (stack.isEmpty()) {
                    markArr[i] = 1;
                }else {
                    // 能匹配的左右括号下标位置
                    markArr[i] = 0;
                    markArr[stack.pop()] = 0;
                }
            }
        }
        // 把stack 中未匹配的左括号 弹出来
        while (!stack.isEmpty()) {
            markArr[stack.pop()] = 1;
        }
        int longest = 0;
        int tempLongest = 0;
        // 找到 markArr 数组中连续0 的最大长度
        for (int i = 0; i < length; i++) {
            if (markArr[i] == 0) {
                tempLongest++;
                longest = Math.max(longest, tempLongest);
            } else {
                tempLongest = 0;
            }
        }
        return longest;
    }

    // 输入：s = ")()())"
    // 输出：4
    // 解释：最长有效括号子串是 "()()"
    // "()(()"
    // 栈：技巧性很强，时间复杂度O(n), 空间复杂度O(n),
    // https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

    static public int longestValidParentheses(String s) {
        if (s == "") return 0;
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }

    // 正向逆向结合，时间复杂度O(n), 空间复杂度O(1),
    static public int longestValidParentheses1(String s) {
        int left = 0;
        int right = 0;
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++;
            else right++;
            if (left == right) maxLength = Math.max(maxLength, left + right);
            if (right > left) left = right = 0;
        }
        left = right = 0;
        for (int j = s.length() - 1; j >= 0; j--) {
            if (s.charAt(j) == '(') left++;
            else right++;
            if (left == right) maxLength = Math.max(maxLength, left + right);
            if (left > right) left = right = 0;
        }
        return maxLength;
    }

}
